/*
 * Hamiltonian path - search algorithm
 * -----------------------------------
 * authors: Jiri Melnikov, Lubos Hnat
 * 
 */

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string.h>
#include <math.h>

using namespace std;

/*** CONSTANTS AND OTHERS ***/
#define DEBUG_MESSAGES
#define EXPORT_TO_FILE
#define EXPORT_TO_IMAGE

#define     STACKSTEP           100


/*** GLOBAL VARIABLES ***/
int nodesCount;
int * nodes;

int * localStack;
int stackPointer;
int stackBottom;
int stackSize;
int stackItemSize;

double * distances;



/*** FUNCTIONS ***/
bool readValuesFromFile(char * file);

int push(int * data);
int pop(int * data);
int popBottom(int * data);
int top(int * data);

double getDistance(int nodeA, int nodeB);
bool generateDistances();
double itemDistance(int * data);

/************************************************************
 * Main function
 ************************************************************/
int main(int argc, char** argv) {
    //File with nodes
    char nodesFilename[] = "/home/kafe/Temp/nodes";
    char plotFilename[] = "/home/kafe/Temp/nodesPlot";
    char graphFilename[] = "/home/kafe/Temp/nodesPlot.png";

    cout << "Shortest Hamiltonian path finder" << endl;
    cout << "--------------------------------" << endl;

#ifdef DEBUG_MESSAGES
    cout << "Reading file with nodes..." << endl;
#endif

    if (!readValuesFromFile(nodesFilename)) {
        cerr << "Reading from file failed. Exiting." << endl;
        return false;
    }

#ifdef DEBUG_MESSAGES
    cout << "Reading completed." << endl;
#endif

    //Pregenerate distances
    generateDistances();

    cout << "Preparations done, we will compute " << nodesCount << " nodes. Running algorithm." << endl;

    //Init stack
    stackItemSize = nodesCount + 1; //size of one stack item
    stackSize = stackItemSize * STACKSTEP;
    localStack = new int[stackSize]; //for first create only basic size of stack
    stackPointer = 0; //set pointer to first item
    stackBottom = 0; //set bottom of stack to null
    int data[stackItemSize];
    int dataTemp[stackItemSize];
    int dataFinal[stackItemSize];
    int * dataPointer;

    //Insert first null elements
    for (int x = 0; x < stackItemSize; x++) {
        data[x] = 0;
        dataTemp[x] = 0;
        dataFinal[x] = 0;
    }
    push(data); //Push firts items to stack

    //Algorithm part
    double minimalDistace = -1;
    while (true) {
        if (stackPointer != stackBottom) {
            pop(data);
            //Check if we have generated all nodes
            if (data[0] != nodesCount) {
                //We haven't, so generate more of them
                //First backup stack item, from which we're generating new data
                for (int x = 0; x < stackItemSize; x++) {
                    dataTemp[x] = data[x];
                }
                //Now generate new series
                int y = 1;
                data[0] = dataTemp[0] + 1;
                for (int x = 0; x < (nodesCount - dataTemp[0]); x++) {
                    //Search for empty space for new number
                    while (data[y] != 0) {
                        y++;
                    }
                    data[y] = data[0];
                    if (minimalDistace > itemDistance(data) || minimalDistace == -1) {
                        push(data); //Insert
                    }
                    //Reload old value
                    data[y] = dataTemp[y++];
                }
            } else {
                //We have final part, now print distance
                double distance = itemDistance(data);
                if (minimalDistace > distance || minimalDistace == -1) {
                    minimalDistace = distance;
#ifdef DEBUG_MESSAGES
                    cout << "New minimal distance found: " << minimalDistace << endl;
#endif
                    for (int x = 0; x < stackItemSize; x++) {
                        dataFinal[x] = data[x];
                    }
                }
            }
        } else {
            minimalDistace = itemDistance(dataFinal);
            dataPointer = &dataFinal[0];
            cout << "Minimal way:" << endl;
            for (int y = 1; y < stackItemSize; y++) {
                cout << nodes[((*(dataPointer + y)) - 1)*2] << " " << nodes[((*(dataPointer + y)) - 1)*2 + 1] << endl;
            }
            cout << "Distance: " << minimalDistace << endl;

#ifdef EXPORT_TO_FILE
            cout << "Exporting to file plot" << endl;
            ofstream exportFile;
            exportFile.open(plotFilename);
            for (int y = 1; y < stackItemSize; y++) {
                exportFile << nodes[((*(dataPointer + y)) - 1)*2] << " " << nodes[((*(dataPointer + y)) - 1)*2 + 1] << endl;
            }
            exportFile.close();
#ifdef EXPORT_TO_IMAGE
            //Run gnu plot
            cout << "Exporting to graph by gnuplot." << endl;
            char * plotCommand = new char[77 + sizeof (plotFilename) + sizeof (graphFilename)];
            memcpy(plotCommand, "echo \"set terminal png; set output '", 36);
            memcpy(&plotCommand[36], graphFilename, sizeof (graphFilename));
            memcpy(&plotCommand[35 + sizeof (graphFilename)], "'; plot '", 9);
            memcpy(&plotCommand[35 + sizeof (graphFilename) + 9], plotFilename, sizeof (plotFilename));
            memcpy(&plotCommand[34 + sizeof (graphFilename) + 9 + sizeof (plotFilename)], "' with linespoints\" | gnuplot\0", 30);
            system(plotCommand);
#endif
#endif

            cout << "--------------------------------" << endl;
            cout << "--------------DONE--------------" << endl;

            //Free memory
            delete [] distances;
            delete [] nodes;
            delete [] localStack;

#ifdef DEBUG_MESSAGES
            cout << "Allocated memory freed." << endl;
#endif

            return (EXIT_SUCCESS);
        }
    }

    return (EXIT_SUCCESS);
}

/************************************************************
 * Reads nodes from defined file
 ************************************************************/
bool readValuesFromFile(char* file) {
    //Define basic variables
    char input[32];
    int numA, numB;
    //Open file
    ifstream importFile(file);
    if (!importFile.is_open()) {
        cerr << "Cannot open file." << endl;
        return false;
    }
    //Read count of nodes
    importFile.getline(input, sizeof (input));
    nodesCount = atoi(input);
    //Check count
    if (nodesCount < 2) {
        cerr << "At least 2 nodes are required." << endl;
        return false;
    }

#ifdef DEBUG_MESSAGES
    cout << nodesCount << " nodes will be loaded." << endl;
#endif

    //We know count, let's create an array with nodes
    nodes = new int[nodesCount * 2];
    for (int x = 0; x < nodesCount; x++) {
        importFile.getline(input, sizeof (input), ' ');
        numA = atoi(input);
        importFile.getline(input, sizeof (input), '\n');
        numB = atoi(input);

        nodes[(x * 2)] = numA;
        nodes[(x * 2) + 1] = numB;
#ifdef DEBUG_MESSAGES
        cout << "Node on " << numA << "x" << numB << " loaded." << endl;
#endif
    }

#ifdef DEBUG_MESSAGES
    cout << "Nodes loaded." << endl;
#endif

    //Close file
    importFile.close();

    return true;
}

/************************************************************
 * Stack push
 ************************************************************/
int push(int * data) {
    for (int x = 0; x < stackItemSize; x++) {
        localStack[stackPointer++] = data[x];
    }
    if (stackPointer == stackSize) {
        int newStackSize = stackSize + (stackItemSize * STACKSTEP);
        int * newLocalStack = new int[newStackSize];
        for (int x = 0; x < stackSize; x++) {
            newLocalStack[x] = localStack[x];
        }
        stackSize = newStackSize;
        delete [] localStack;
        localStack = newLocalStack;
    }
}

/************************************************************
 * Stack pop
 ************************************************************/
int pop(int * data) {
    stackPointer -= stackItemSize;
    for (int x = 0; x < stackItemSize; x++) {
        data[x] = localStack[stackPointer++];
    }
    stackPointer -= stackItemSize;
}

/************************************************************
 * Stack pop from bottom
 ************************************************************/
int popBottom(int * data) {
    for (int x = 0; x < stackItemSize; x++) {
        data[x] = localStack[stackBottom++];
    }
}

/************************************************************
 * Stack top
 ************************************************************/
int top(int * data) {
    stackPointer -= stackItemSize;
    for (int x = 0; x < stackItemSize; x++) {
        data[x] = localStack[stackPointer++];
    }
}

/************************************************************
 * Compute distance
 ************************************************************/
double getDistance(int nodeA, int nodeB) {
    double distance = 0;
    distance += pow((nodes[(nodeA * 2)] - nodes[(nodeB * 2)]), 2);
    distance += pow((nodes[(nodeA * 2) + 1] - nodes[(nodeB * 2) + 1]), 2);
    distance = sqrt(distance);
    return distance;
}

/************************************************************
 * Pregenerates all distances
 ************************************************************/
bool generateDistances() {
    int distancesCount = pow(nodesCount, 2);
    distances = new double[distancesCount];
    for (int x = 0; x < nodesCount; x++) {
        for (int y = 0; y < nodesCount; y++) {
            distances[x + y * nodesCount] = getDistance(x, y);
        }
    }
}

/************************************************************
 * Get distance of whole row
 ************************************************************/
double itemDistance(int * data) {
    double distance = 0;
    int x = 1, y;
    while (x < (stackItemSize - 1)) {
        while (data[x] == 0) {
            x++;
        }
        y = x + 1;
        while (data[y] == 0) {
            y++;
        }
        if (y < stackItemSize) distance += distances[(data[x] - 1) + ((data[y] - 1) * nodesCount)];
        x++;
    }
    return distance;
}